{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find K Pairs with Smallest Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kSmallestPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找和最小的 K 对数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个以 <strong>非递减顺序排列</strong> 的整数数组 <code>nums1</code> 和<strong> </strong><code>nums2</code><strong>&nbsp;</strong>,&nbsp;以及一个整数 <code>k</code><strong>&nbsp;</strong>。</p>\n",
    "\n",
    "<p>定义一对值&nbsp;<code>(u,v)</code>，其中第一个元素来自&nbsp;<code>nums1</code>，第二个元素来自 <code>nums2</code><strong>&nbsp;</strong>。</p>\n",
    "\n",
    "<p>请找到和最小的 <code>k</code>&nbsp;个数对&nbsp;<code>(u<sub>1</sub>,v<sub>1</sub>)</code>, <code>&nbsp;(u<sub>2</sub>,v<sub>2</sub>)</code> &nbsp;... &nbsp;<code>(u<sub>k</sub>,v<sub>k</sub>)</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [1,7,11], nums2 = [2,4,6], k = 3\n",
    "<strong>输出:</strong> [1,2],[1,4],[1,6]\n",
    "<strong>解释: </strong>返回序列中的前 3 对数：\n",
    "     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums1 = [1,1,2], nums2 = [1,2,3], k = 2\n",
    "<strong>输出: </strong>[1,1],[1,1]\n",
    "<strong>解释: </strong>返回序列中的前 2 对数：\n",
    "&nbsp;    [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums1 = [1,2], nums2 = [3], k = 3 \n",
    "<strong>输出:</strong> [1,3],[2,3]\n",
    "<strong>解释: </strong>也可能序列中所有的数对都被返回:[1,3],[2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums1</code> 和 <code>nums2</code> 均为升序排列</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-k-pairs-with-smallest-sums](https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-k-pairs-with-smallest-sums](https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7,11]\\n[2,4,6]\\n3', '[1,1,2]\\n[1,2,3]\\n2', '[1,2]\\n[3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        queue = [[nums1[0]+nums2[0], 0, 0]]\n",
    "        def push(i,j):\n",
    "            nonlocal queue\n",
    "            heapq.heappush(queue, [nums1[i]+nums2[j], i, j])\n",
    "        # for i in range(len(nums1)):\n",
    "        #     push(i, 0)\n",
    "        result = []\n",
    "        while queue and k > 0:\n",
    "            k -= 1\n",
    "            _, i, j = heapq.heappop(queue)\n",
    "            result.append([nums1[i], nums2[j]])\n",
    "            if j == 0 and i + 1 < len(nums1):\n",
    "                push(i+1, 0)\n",
    "            if j + 1 < len(nums2):\n",
    "                push(i, j+1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "\n",
    "        # 二分查找第 k 小的数对和\n",
    "        left, right = nums1[0] + nums2[0], nums1[m - 1] + nums2[n - 1] + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = 0\n",
    "            i, j = 0, n - 1\n",
    "            while i < m and j >= 0:\n",
    "                if nums1[i] + nums2[j] > mid:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    cnt += j + 1\n",
    "                    i += 1\n",
    "            if cnt < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        pairSum = left\n",
    "\n",
    "        ans = []\n",
    "        # 找数对和小于 pairSum 的数对\n",
    "        i = n - 1\n",
    "        for num1 in nums1:\n",
    "            while i >= 0 and num1 + nums2[i] >= pairSum:\n",
    "                i -= 1\n",
    "            for j in range(i + 1):\n",
    "                ans.append([num1, nums2[j]])\n",
    "                if len(ans) == k:\n",
    "                    return ans\n",
    "\n",
    "        # 找数对和等于 pairSum 的数对\n",
    "        i = n - 1\n",
    "        for num1 in nums1:\n",
    "            while i >= 0 and num1 + nums2[i] > pairSum:\n",
    "                i -= 1\n",
    "            j = i\n",
    "            while j >= 0 and num1 + nums2[j] == pairSum:\n",
    "                ans.append([num1, nums2[j]])\n",
    "                if len(ans) == k:\n",
    "                    return ans\n",
    "                j -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "\n",
    "        # 二分查找第 k 小的数对和\n",
    "        left, right = nums1[0] + nums2[0], nums1[m - 1] + nums2[n - 1] + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = 0\n",
    "            i, j = 0, n - 1\n",
    "            while i < m and j >= 0:\n",
    "                if nums1[i] + nums2[j] > mid:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    cnt += j + 1\n",
    "                    i += 1\n",
    "            if cnt < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        pairSum = left\n",
    "\n",
    "        ans = []\n",
    "        # 找数对和小于 pairSum 的数对\n",
    "        i = n - 1\n",
    "        for num1 in nums1:\n",
    "            while i >= 0 and num1 + nums2[i] >= pairSum:\n",
    "                i -= 1\n",
    "            for j in range(i + 1):\n",
    "                ans.append([num1, nums2[j]])\n",
    "                if len(ans) == k:\n",
    "                    return ans\n",
    "\n",
    "        # 找数对和等于 pairSum 的数对\n",
    "        i = n - 1\n",
    "        for num1 in nums1:\n",
    "            while i >= 0 and num1 + nums2[i] > pairSum:\n",
    "                i -= 1\n",
    "            j = i\n",
    "            while j >= 0 and num1 + nums2[j] == pairSum:\n",
    "                ans.append([num1, nums2[j]])\n",
    "                if len(ans) == k:\n",
    "                    return ans\n",
    "                j -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        h = [(nums1[0] + nums2[0], 0, 0)]\n",
    "        while h and len(ans) < k:\n",
    "            _, i, j = heappop(h)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if j == 0 and i + 1 < len(nums1):\n",
    "                heappush(h, (nums1[i + 1] + nums2[0], i + 1, 0))\n",
    "            if j + 1 < len(nums2):\n",
    "                heappush(h, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        return ans\n",
    "\n",
    "#作者：灵茶山艾府\n",
    "#链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/2286318/jiang-qing-chu-wei-shi-yao-yi-kai-shi-ya-i0dj/\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        pq = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, m))]\n",
    "        while pq and len(ans) < k:\n",
    "            _, i, j = heappop(pq)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < n:\n",
    "                heappush(pq, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        h = [(nums1[0] + nums2[j], 0, j) for j in range(min(k, n2))]\n",
    "        ans = []\n",
    "        while h and len(ans) < k:\n",
    "            _, i, j = heapq.heappop(h)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if i < n1 - 1:\n",
    "                heapq.heappush(h, (nums1[i + 1] + nums2[j], i + 1, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self):\n",
    "        self.list = []\n",
    "        self.size = 0\n",
    "    \n",
    "\n",
    "    def heapify(self,i):\n",
    "        arr = self.list\n",
    "        end = self.size - 1\n",
    "\n",
    "        while 2*i + 1 <= end:\n",
    "            smallest = 2 * i + 1\n",
    "\n",
    "            if smallest + 1 <= end and arr[smallest+1][0] < arr[smallest][0]:\n",
    "                smallest += 1\n",
    "            \n",
    "            if arr[smallest][0] < arr[i][0]:\n",
    "                arr[i],arr[smallest] = arr[smallest],arr[i]\n",
    "                i = smallest\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    def pop(self):\n",
    "        arr = self.list\n",
    "\n",
    "        arr[0],arr[-1] = arr[-1],arr[0]\n",
    "        pop = arr.pop()\n",
    "\n",
    "        self.size -= 1\n",
    "        self.heapify(0)\n",
    "\n",
    "        return pop\n",
    "    \n",
    "    def heapInsert(self,i):\n",
    "        arr = self.list\n",
    "\n",
    "        while i > 0:\n",
    "            father = (i-1) // 2\n",
    "\n",
    "            if arr[i][0] < arr[father][0]:\n",
    "                arr[i],arr[father] = arr[father],arr[i]\n",
    "                i = father\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    def push(self,tup):\n",
    "        self.list.append(tup)\n",
    "        self.size += 1\n",
    "        self.heapInsert(self.size - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "        heap = Heap()\n",
    "\n",
    "        for i in range(min(k,n2)): # better than range(n2)\n",
    "            heap.push((nums1[0]+nums2[i],0,i))\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        while k>0 and heap.list:\n",
    "            s,i,j = heap.pop()\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            k -= 1\n",
    "            \n",
    "            if i+1 < n1:\n",
    "                heap.push((nums1[i+1]+nums2[j],i+1,j))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        pq =[(nums1[i] + nums2[0], i, 0) for i in range(min(k, m))]\n",
    "        while pq and len(ans) < k:\n",
    "            _, i, j = heappop(pq)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < n:\n",
    "                heappush(pq, (nums1[i] + nums2[j + 1], i, j+ 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        flag = m<n\n",
    "        res = []  \n",
    "        if not flag:\n",
    "            m, n, nums1, nums2 = n, m, nums2, nums1\n",
    "        pq = []\n",
    "        for i in range(min(m,k)):\n",
    "            heapq.heappush(pq,(nums1[i]+nums2[0],i,0))\n",
    "        while len(res) <k and pq:\n",
    "            _, a, b = heapq.heappop(pq)\n",
    "            res.append([nums1[a],nums2[b]] if flag else [nums2[b],nums1[a]])\n",
    "            if b+1 < n:\n",
    "                heapq.heappush(pq, (nums1[a]+nums2[b+1],a, b+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        h=[(nums1[i]+nums2[0],i,0) for i in range(min(len(nums1),k))]\n",
    "        while h and len(ans)<k:\n",
    "            _, i, j = heappop(h)\n",
    "            ans.append([nums1[i],nums2[j]])\n",
    "            if j+1<len(nums2):\n",
    "                heappush(h,(nums1[i]+nums2[j+1],i,j+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self,nums1:List[int],nums2:List[int],k:int)->List[List[int]]:\n",
    "        ans=[]\n",
    "        h=[(nums1[0]+nums2[0],0,0)]\n",
    "        while h and len(ans)<k:\n",
    "            _,i,j=heapq.heappop(h)\n",
    "            ans.append([nums1[i],nums2[j]])\n",
    "            if j==0 and i+1<len(nums1):\n",
    "                heapq.heappush(h,(nums1[i+1]+nums2[0],i+1,0))\n",
    "            if j+1<len(nums2):\n",
    "                heapq.heappush(h,(nums1[i]+nums2[j+1],i,j+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        res = []\n",
    "        queue = []\n",
    "        if not nums1 or not nums2:\n",
    "            return []\n",
    "        heapq.heappush(queue, (nums1[0] + nums2[0], (0, 0)))\n",
    "        # 防止重复加入\n",
    "        visited = {(0, 0)}\n",
    "        while queue and len(res) < k:\n",
    "            _, (i, j) = heapq.heappop(queue)\n",
    "            res.append((nums1[i], nums2[j]))\n",
    "            # 每次nums1 或者 nums2 移动\n",
    "            if i + 1 < len(nums1) and (i + 1, j) not in visited:\n",
    "                heapq.heappush(queue, (nums1[i + 1] + nums2[j], (i + 1, j)))\n",
    "                visited.add((i + 1, j))\n",
    "            if j + 1 < len(nums2) and (i, j + 1) not in visited:\n",
    "                heapq.heappush(queue, (nums1[i] + nums2[j + 1], (i, j + 1)))\n",
    "                visited.add((i, j + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "            heap = []\n",
    "            heapq.heappush(heap, (nums1[0] + nums2[0], (0, 0)))\n",
    "            seen = set([(0, 0)])\n",
    "            result = []\n",
    "            m, n = len(nums1), len(nums2)\n",
    "\n",
    "            while heap and k > 0:\n",
    "                _, (i, j) = heapq.heappop(heap)\n",
    "                result.append([nums1[i], nums2[j]])\n",
    "                k -= 1\n",
    "\n",
    "                if i + 1 < m and (i + 1, j) not in seen:\n",
    "                    heapq.heappush(heap, (nums1[i + 1] + nums2[j], (i + 1, j)))\n",
    "                    seen.add((i + 1, j))\n",
    "\n",
    "                if j + 1 < n and (i, j + 1) not in seen:\n",
    "                    heapq.heappush(heap, (nums1[i] + nums2[j + 1], (i, j + 1)))\n",
    "                    seen.add((i, j + 1))\n",
    "\n",
    "            return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        q = [(nums1[0] + nums2[0], 0, 0)]\n",
    "        ans = []\n",
    "        vis = {(0, 0)}\n",
    "        while k and q:\n",
    "            _, i, j = heapq.heappop(q)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if i + 1 < m:\n",
    "                if (i + 1, j) not in vis:\n",
    "                    heapq.heappush(q, (nums1[i + 1] + nums2[j], i + 1, j))\n",
    "                    vis.add((i + 1, j))\n",
    "            if j + 1 < n:\n",
    "                if (i, j + 1) not in vis:\n",
    "                    heapq.heappush(q, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "                    vis.add((i, j + 1))\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "\n",
    "        res = []\n",
    "        # heap里存储 两者的和，nums1的下标，nums2的下标\n",
    "        heap = [(nums1[0]+nums2[0],0,0)]\n",
    "        repeat = set() # 记录重复组合\n",
    "        while  len(res) < k:\n",
    "            if not heap:\n",
    "                return res \n",
    "            summ,i,j = heapq.heappop(heap) # 取出最小值信息\n",
    "            # sum为和， i 和j分别记录 nums1和nums2的下标值\n",
    "            \n",
    "            if (i,j) in repeat: # 重复值去掉\n",
    "                continue\n",
    "            repeat.add((i,j)) \n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            \n",
    "\t\t\t# 按照展开思路  取1存2\n",
    "            if i+1<len(nums1):\n",
    "                heapq.heappush(heap,(nums1[i+1]+nums2[j],i+1,j))\n",
    "            if j +1 <len(nums2):\n",
    "                heapq.heappush(heap,(nums1[i]+nums2[j+1],i,j+1))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        dict1=collections.defaultdict(list)\n",
    "        result=[]\n",
    "        heap1=[]\n",
    "        heapq.heapify(heap1)\n",
    "\n",
    "        for i in range(k):\n",
    "            if i<len(nums1) and len(dict1[i])==0:\n",
    "                heapq.heappush(heap1,[nums1[i]+nums2[0],i,0])\n",
    "                dict1[i].append(0)\n",
    "            if len(heap1)==0:\n",
    "                break\n",
    "            temp1=heapq.heappop(heap1)\n",
    "            nums1_index=temp1[1]\n",
    "            num2_index=temp1[2]\n",
    "            result.append([nums1[nums1_index],nums2[num2_index]])\n",
    "\n",
    "            if num2_index==len(nums2)-1:\n",
    "                continue\n",
    "            else:\n",
    "                list1=dict1[nums1_index]\n",
    "                if list1==[]:\n",
    "                    heapq.heappush(heap1,[nums1[nums1_index]+nums2[num2_index+1],nums1_index,num2_index+1])\n",
    "                    dict1[nums1_index].append(num2_index+1)\n",
    "                else:\n",
    "                    now_index=list1[-1]\n",
    "                    if now_index<len(nums2)-1:\n",
    "                        heapq.heappush(heap1,[nums1[nums1_index]+nums2[now_index+1],nums1_index,now_index+1])\n",
    "                        dict1[nums1_index].append(now_index+1)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        l=0;r=0;n1=len(nums1);n2=len(nums2);ans=[];a=[]\n",
    "        while (l)*(r)<k:\n",
    "            if r<n2 and l< n1 and nums1[l]>nums2[r]:r+=1\n",
    "            elif l<n1:l+=1\n",
    "            if r>=n2:l+=1\n",
    "            elif l>=n1:r+=1\n",
    "        for i,j in  product(nums1[:l+50],nums2[:r+50]):\n",
    "            ans.append([i,j,i+j])\n",
    "        ans.sort(key=lambda x:(x[2],-x[0]))    \n",
    "        for i in ans[:k]:\n",
    "            a.append([i[0],i[1]])\n",
    "        return (a)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        \n",
    "        \n",
    "        # 分情况讨论\n",
    "        # 如果k大于nums1以及nums2的len，则需要求不同情况\n",
    "        # 如果k小于nums1的len但是大于nums2的len，则可以固定nums2的最小值，即最小的k个pair的其中一个数字一定是nums2的最小值\n",
    "        # 如果k小于nums2的len但是大于nums1的len，与上面相反\n",
    "        # 如果比两者的len都小，则每个pair都取两个nums的最小值的小者，另一个按排序k即可\n",
    "        \n",
    "        if not nums1 or not nums2:\n",
    "            return []\n",
    "        \n",
    "        # 如果k要大于两者的所有组合个数，则直接返回所有组合即可\n",
    "        if k>=(len(nums1)*len(nums2)):\n",
    "            results = []\n",
    "            for i in range(len(nums1)):\n",
    "                for j in range(len(nums2)):\n",
    "                    results.append([nums1[i], nums2[j]])\n",
    "\n",
    "            return results\n",
    "\n",
    "        # 如果k小于两者的所有组合个数，则一个一个添加，直到数组大于k\n",
    "        # 维护一个最大堆，遍历所有可能性\n",
    "\n",
    "        else:\n",
    "\n",
    "            results = []\n",
    "            for i in range(len(nums1)):\n",
    "                for j in range(len(nums2)):\n",
    "                    results.append([nums1[i], nums2[j]])\n",
    "\n",
    "            return heapq.nsmallest(k, results, key=lambda x:x[0]+x[1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                        \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        pq = Heap()\n",
    "        for i in range(len(nums1)):\n",
    "            pq.insert((nums1[i], nums2[0], 0))\n",
    "\n",
    "        res = []\n",
    "        while pq.size and k > 0:\n",
    "            cur = pq.del_min()\n",
    "            k -= 1\n",
    "            nxt = cur[2] + 1\n",
    "            if nxt < len(nums2):\n",
    "                pq.insert((cur[0], nums2[nxt], nxt))\n",
    "\n",
    "            res.append([cur[0], cur[1]])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class Heap:\n",
    "\n",
    "    def __init__(self):\n",
    "\n",
    "        self.pq = [(0, 0, 0)]\n",
    "        self.size = 0\n",
    "\n",
    "    def swim(self, i):\n",
    "\n",
    "        while i > 1 and self.more(self.parent(i), i):\n",
    "            self.swap(self.parent(i), i)\n",
    "            i = self.parent(i)\n",
    "\n",
    "    def sink(self, i):\n",
    "\n",
    "        while self.left(i) <= self.size:\n",
    "            tmp_min = self.left(i)\n",
    "            if self.right(i) <= self.size and self.more(tmp_min, self.right(i)):\n",
    "                tmp_min = self.right(i)\n",
    "            if self.more(tmp_min, i):\n",
    "                break\n",
    "            self.swap(tmp_min, i)\n",
    "            i = tmp_min\n",
    "\n",
    "    def insert(self, x):\n",
    "\n",
    "        self.pq.append(x)\n",
    "        self.size += 1\n",
    "        self.swim(self.size)\n",
    "\n",
    "    def del_min(self):\n",
    "\n",
    "        res = self.pq[1]\n",
    "        self.swap(1, self.size)\n",
    "        self.pq.pop()\n",
    "        self.size -= 1\n",
    "        self.sink(1)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def swap(self, i, j):\n",
    "\n",
    "        self.pq[i], self.pq[j] = self.pq[j], self.pq[i]\n",
    "\n",
    "    def more(self, i, j):\n",
    "\n",
    "        return True if self.pq[i][0] + self.pq[i][1] > self.pq[j][0] + self.pq[j][1] else False\n",
    "\n",
    "    def min(self):\n",
    "\n",
    "        return self.pq[1]\n",
    "\n",
    "    def left(self, i):\n",
    "\n",
    "        return 2 * i\n",
    "\n",
    "    def right(self, i):\n",
    "\n",
    "        return 2 * i + 1\n",
    "\n",
    "    def parent(self, i):\n",
    "\n",
    "        return i // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        # ans = []\n",
    "        # # 存储k个或者nums1的人长度\n",
    "        # h = [(nums1[i]+nums2[0], i, 0) for i in range(min(len(nums1), k))]\n",
    "\n",
    "        # while h and len(ans) < k:\n",
    "        #     _, i, j = heappop(h)\n",
    "        #     ans.append([nums1[i], nums2[j]])\n",
    "        #     if j + 1 < len(nums2):\n",
    "        #         heappush(h, (nums1[i]+nums2[j+1], i, j+1))\n",
    "        # return ans\n",
    "\n",
    "        ans = []\n",
    "        same = set()\n",
    "        h = [(nums1[0] + nums2[0], 0, 0)]\n",
    "        while h and len(ans) < k:\n",
    "            # 弹出最小元素\n",
    "            _, i, j = heappop(h)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            print()\n",
    "            # 加入两个元素\n",
    "            if i + 1 < len(nums1) and (i+1, j) not in same:\n",
    "                heappush(h, (nums1[i+1] + nums2[j], i+1, j))\n",
    "                same.add((i+1, j))\n",
    "            if j + 1 < len(nums2) and (i, j+1) not in same:\n",
    "                heappush(h, (nums1[i] + nums2[j+1], i, j+1))\n",
    "                same.add((i, j+1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(len(nums2)):\n",
    "                result.append([nums1[i], nums2[j]])\n",
    "        return heapq.nsmallest(k, result, key=lambda lst: lst[0]+lst[1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        return heapq.nsmallest(k, [[i, j] for i in nums1 for j in nums2], key=sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        if not nums2 or not nums1:\n",
    "            return []\n",
    "        result = []\n",
    "        heap = []\n",
    "\n",
    "        queues = []\n",
    "        for n1 in nums1:\n",
    "            q = deque()\n",
    "            for n2 in nums2:\n",
    "                q.append([n1, n2])\n",
    "            queues.append(q)\n",
    "\n",
    "        for q in queues:\n",
    "            n1, n2 = q.popleft()\n",
    "            heapq.heappush(heap, (n1 + n2, n1, n2, q))\n",
    "\n",
    "        while len(result) < k and heap:\n",
    "            _, n1, n2, q = heapq.heappop(heap)\n",
    "            result.append([n1, n2])\n",
    "\n",
    "            if q:\n",
    "                n1, n2 = q.popleft()\n",
    "                heapq.heappush(heap, (n1 + n2, n1, n2, q))\n",
    "\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ret = []\n",
    "        merge_list = [(i, 0) for i in range(len(nums1))]\n",
    "        for _ in range(k):\n",
    "            if not merge_list:\n",
    "                return ret\n",
    "            pop_i, pop_j = merge_list.pop(0)\n",
    "            ret.append((nums1[pop_i], nums2[pop_j]))\n",
    "            pop_j += 1\n",
    "            if pop_j >= len(nums2):\n",
    "                continue\n",
    "            insert_sum = nums1[pop_i] + nums2[pop_j]\n",
    "            left = 0\n",
    "            right = len(merge_list) - 1\n",
    "            index = None\n",
    "            while left <= right:\n",
    "                index = left + (right - left) // 2\n",
    "                index_i, index_j = merge_list[index]\n",
    "                index_sum = nums1[index_i] + nums2[index_j]\n",
    "                if index_sum == insert_sum:\n",
    "                    break\n",
    "                elif index_sum > insert_sum:\n",
    "                    right = index - 1\n",
    "                else:\n",
    "                    left = index + 1\n",
    "            if left > right:\n",
    "                index = left\n",
    "            merge_list.insert(index, (pop_i, pop_j))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        return heapq.nsmallest(k, [[i, j] for i in nums1 for j in nums2], key=lambda x: x[0]+x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        class P:\n",
    "            def __init__(self, x, y):\n",
    "                self.x = x\n",
    "                self.y = y\n",
    "                self.s = nums1[x] + nums2[y]\n",
    "            def __lt__(self, other):\n",
    "                if self.s < other.s:\n",
    "                    return True\n",
    "                return False\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(0, min(k, len(nums1))):\n",
    "            heapq.heappush(queue, P(i, 0))\n",
    "        \n",
    "        res = []\n",
    "        while len(res) < k and len(queue) > 0:\n",
    "            min_pair = heapq.heappop(queue)\n",
    "            if min_pair.y + 1 < len(nums2):\n",
    "                heapq.heappush(queue, P(min_pair.x, min_pair.y + 1))\n",
    "            res.append([nums1[min_pair.x], nums2[min_pair.y]])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Node:\n",
    "\n",
    "    list_a: List[int] = None\n",
    "    list_b: List[int] = None\n",
    "\n",
    "    def __init__(self, a_i: int, b_i: int):\n",
    "        self.a_i = a_i\n",
    "        self.b_i = b_i\n",
    "        self.value = Node.list_a[a_i] + Node.list_b[b_i]\n",
    "\n",
    "    def __lt__(self, other: 'Node') -> bool:\n",
    "        if self.value < other.value:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def k_smallest_pairs_v1(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        Node.list_a = nums1\n",
    "        Node.list_b = nums2\n",
    "        len_n1 = len(nums1)\n",
    "        len_n2 = len(nums2)\n",
    "        a_i = 0\n",
    "        b_i = 0\n",
    "        container = []\n",
    "        skip_set = set()\n",
    "        node = Node(a_i, b_i)\n",
    "        heapq.heappush(container, node)\n",
    "        skip_set.add((a_i, b_i))\n",
    "        rst = []\n",
    "        while container and k > 0:\n",
    "            node = heapq.heappop(container)\n",
    "            rst.append([nums1[node.a_i], nums2[node.b_i]])\n",
    "            k -= 1\n",
    "            if k == 0:\n",
    "                break\n",
    "            n_pos = (node.a_i, node.b_i + 1)\n",
    "            if n_pos[0] < len_n1 and n_pos[1] < len_n2 and n_pos not in skip_set:\n",
    "                new_node = Node(*n_pos)\n",
    "                heapq.heappush(container, new_node)\n",
    "                skip_set.add(n_pos)\n",
    "            n_pos = (node.a_i + 1, node.b_i)\n",
    "            if n_pos[0] < len_n1 and n_pos[1] < len_n2 and n_pos not in skip_set:\n",
    "                new_node = Node(*n_pos)\n",
    "                heapq.heappush(container, new_node)\n",
    "                skip_set.add(n_pos)\n",
    "        return rst\n",
    "\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        return self.k_smallest_pairs_v1(nums1, nums2, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        list_ = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                list_.append([i,j])\n",
    "        return heapq.nsmallest(k, list_, key = sum)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        heap = [0]\n",
    "        def push(heap,site):\n",
    "            heap.append(site)\n",
    "            i = len(heap)-1\n",
    "            while i//2 >=1:\n",
    "                parent_value = nums1[heap[i//2][0]]+nums2[heap[i//2][1]]\n",
    "                value = nums1[heap[i][0]]+nums2[heap[i][1]]\n",
    "                if parent_value > value:\n",
    "                    t = heap[i//2]\n",
    "                    heap[i//2] = heap[i]\n",
    "                    heap[i] = t\n",
    "                    i=i//2\n",
    "                else:\n",
    "                    break\n",
    "        def pop(heap):\n",
    "            r = heap[1]\n",
    "            if heap[1][0]+1 < len(nums1):\n",
    "                heap[1] = (heap[1][0]+1, heap[1][1])\n",
    "            elif len(heap)==2:\n",
    "                return heap.pop()\n",
    "            else:\n",
    "                heap[1] = heap.pop()\n",
    "            i = 1\n",
    "            while i*2 < len(heap):\n",
    "                value = nums1[heap[i][0]]+nums2[heap[i][1]]\n",
    "                left_value = nums1[heap[i*2][0]]+nums2[heap[i*2][1]]\n",
    "                if i*2+1<len(heap):\n",
    "                    right_value = nums1[heap[i*2+1][0]]+nums2[heap[i*2+1][1]]\n",
    "                    if left_value<=right_value and left_value<value:\n",
    "                        t = heap[i]\n",
    "                        heap[i] = heap[i*2]\n",
    "                        heap[i*2] = t\n",
    "                        i = i*2\n",
    "                    elif left_value>right_value and right_value<value:\n",
    "                        t = heap[i]\n",
    "                        heap[i] = heap[i*2+1]\n",
    "                        heap[i*2+1] = t\n",
    "                        i = i*2+1\n",
    "                    else:\n",
    "                        break\n",
    "                elif left_value<value:\n",
    "                    t = heap[i]\n",
    "                    heap[i] = heap[i*2]\n",
    "                    heap[i*2] = t\n",
    "                    i = i*2\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            return r\n",
    "\n",
    "\n",
    "        for i in range(len(nums2)):\n",
    "            push(heap,(0,i))\n",
    "        result = []\n",
    "        for i in range(k):\n",
    "            site = pop(heap)\n",
    "            result.append((nums1[site[0]],nums2[site[1]]))\n",
    "            if len(heap)==1:\n",
    "                break\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        flag = 1\n",
    "        if m < n:\n",
    "            flag = -1\n",
    "            m, n, nums1, nums2 = n, m, nums2, nums1\n",
    "        \n",
    "        ans = []\n",
    "        heap = [(nums1[0] + x, 0, x) for x in nums2]\n",
    "        heapify(heap)\n",
    "\n",
    "        for _ in range(k):\n",
    "            if not heap:\n",
    "                break\n",
    "            _, i, x2 = heappop(heap)\n",
    "            ans.append([nums1[i], x2][::flag])\n",
    "            if i < m - 1:\n",
    "                heappush(heap, (nums1[i + 1] + x2, i + 1, x2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        flag = 1\n",
    "        if m < n:\n",
    "            flag = -1\n",
    "            m, n, nums1, nums2 = n, m, nums2, nums1\n",
    "        \n",
    "        ans = []\n",
    "        heap = [(nums1[0] + x, 0, x) for x in nums2]\n",
    "\n",
    "        for _ in range(k):\n",
    "            if not heap:\n",
    "                break\n",
    "            _, i, x2 = heappop(heap)\n",
    "            ans.append([nums1[i], x2][::flag])\n",
    "            if i < m - 1:\n",
    "                heappush(heap, (nums1[i + 1] + x2, i + 1, x2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        h=[(i+nums2[0],0) for i in nums1]\n",
    "        heapify(h)\n",
    "        ans=[]\n",
    "        n=len(nums2)\n",
    "        for _ in range(k):\n",
    "            if not h:break\n",
    "            v,cnt=heappop(h)\n",
    "            ans.append((v-nums2[cnt],nums2[cnt]))\n",
    "            if cnt<n-1:heappush(h,(v-nums2[cnt]+nums2[cnt+1],cnt+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        pq = [(nums1[0] + nums2[i], 0, i) for i in range(n2)]\n",
    "        res = []\n",
    "        while k and pq:\n",
    "            a,left,right = heappop(pq)\n",
    "            res.append([nums1[left],nums2[right]])\n",
    "            if left + 1 < n1 :\n",
    "                heappush(pq,(nums1[left+1]+nums2[right],left+1,right))\n",
    "            k -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n, m = len(nums1), len(nums2)\n",
    "        if m * n == 0:\n",
    "            return [] \n",
    "        \n",
    "        # min_heap = [(nums1[0] + nums2[0], 0, 0)]\n",
    "        # res = []\n",
    "        # heapq.heapify(min_heap)\n",
    "        # seen = set()\n",
    "\n",
    "        # while len(min_heap) and len(res) < k:\n",
    "        #     num, r, c = heapq.heappop(min_heap)\n",
    "        #     res.append([nums1[r], nums2[c]])\n",
    "        #     if r < n - 1 and (r+1, c) not in seen:\n",
    "        #         heapq.heappush(min_heap, (nums1[r+1] + nums2[c], r+1, c))\n",
    "        #         seen.add((r+1, c))\n",
    "        #     if c < m - 1 and (r, c+1) not in seen :\n",
    "        #         heapq.heappush(min_heap, (nums1[r] + nums2[c+1], r, c+1))\n",
    "        #         seen.add((r, c+1))\n",
    "        \n",
    "        # return res\n",
    "\n",
    "        min_heap = []\n",
    "        for i in range(n):\n",
    "            min_heap.append((nums1[i] + nums2[0], i, 0))\n",
    "        heapq.heapify(min_heap)\n",
    "        res = []\n",
    "\n",
    "        while min_heap and len(res) < k:\n",
    "            _, r, c = heapq.heappop(min_heap)\n",
    "            res.append([nums1[r], nums2[c]])\n",
    "            \n",
    "            if c < m - 1:\n",
    "                heapq.heappush(min_heap, (nums1[r] + nums2[c+1], r, c+1))\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        class Item:\n",
    "            def __init__(self, i, j):\n",
    "                self.i, self.j = i, j\n",
    "\n",
    "            def __lt__(self, other):\n",
    "                return True if nums1[self.i] + nums2[self.j] < nums1[other.i] + nums2[other.j] else False\n",
    "\n",
    "        priority_q = []\n",
    "        for i in range(min(k, len(nums1))):\n",
    "            heapq.heappush(priority_q, Item(i, 0))\n",
    "\n",
    "        ret = []\n",
    "        while len(ret) < k and len(priority_q) > 0:\n",
    "            largest_one = heapq.heappop(priority_q)\n",
    "            i, j = largest_one.i, largest_one.j\n",
    "            ret.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < len(nums2): heapq.heappush(priority_q, Item(i, j + 1))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import heapq\n",
    "# from typing import List\n",
    "#\n",
    "#\n",
    "# class Solution:\n",
    "#     def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "#         n1 = len(nums1)\n",
    "#         n2 = len(nums2)\n",
    "#         pointers = [0] * n1   # pointers[i]表示nums1[i]参与的最小pair（还未被使用）中，另一个数在nums2中的下标\n",
    "#\n",
    "#         q = []  # pair的最小堆\n",
    "#         for i in range(n1):\n",
    "#             index_2 = pointers[i]\n",
    "#             heapq.heappush(q, (nums1[i]+nums2[index_2], i))\n",
    "#\n",
    "#         res = []\n",
    "#         while len(res) < min(k, n1 * n2):\n",
    "#             sum, index_1 = heapq.heappop(q)\n",
    "#             index_2 = pointers[index_1]\n",
    "#             res.append([nums1[index_1], nums2[index_2]])\n",
    "#\n",
    "#             pointers[index_1] += 1\n",
    "#             if (index_2 := pointers[index_1]) < n2:\n",
    "#                 heapq.heappush(q, (nums1[index_1]+nums2[index_2], index_1))\n",
    "#\n",
    "#         return res\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # the number of pairs smaller than (a_i, b_j) is >= (i+1)*(j+1) - 1\n",
    "        #      (a_0, b_0), ...,   ...,      (a_i, b_0),\n",
    "        #      (a_0, b_1), ...,   ...,      (a_i, b_1)\n",
    "        #       ...\n",
    "        #      (a_0, b_j), ..., (a_i-1, b_j)\n",
    "        # therefore, the pair of (i, j) we may consider must satisfy (i+1)*(j+1) - 1 < k\n",
    "        # i.e. the number of pairs we may consider is roughly\n",
    "        #       k/1 + k/2 + ... + k/k \\approx k\\log k\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        res = []\n",
    "        for i in range(min(n1, k)):\n",
    "            upper_bound = ((k+1) // (i+1)) - 1\n",
    "            if (k+1) % (i+1) != 0:\n",
    "                upper_bound += 1\n",
    "\n",
    "            for j in range(min(n2, upper_bound)):\n",
    "                res.append([nums1[i], nums2[j]])\n",
    "            \n",
    "        res.sort(key=lambda pair: pair[0]+pair[1])\n",
    "\n",
    "\n",
    "        return res[: k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        l,r = 0,0\n",
    "        bl,br = nums1[0],nums2[0]\n",
    "        nums1 = [i-bl for i in nums1]\n",
    "        nums2 = [i-br for i in nums2]\n",
    "        m,n = len(nums1),len(nums2)\n",
    "        k = min(k,m*n)\n",
    "        f = [[0,0]]\n",
    "        v = set('0,0')\n",
    "        def add(l,r):\n",
    "            if f'{l},{r}' in v:\n",
    "                return\n",
    "            t = bisect_left(f,nums1[l]+nums2[r],key=lambda x:nums1[x[0]]+nums2[x[1]])\n",
    "            f.insert(t,[l,r])\n",
    "            v.add(f'{l},{r}')\n",
    "            if len(f)>k-len(res):\n",
    "                f.pop()\n",
    "        res = []\n",
    "        for i in range(min(k,m*n)):\n",
    "            l,r = f.pop(0)\n",
    "            res.append([nums1[l]+bl,nums2[r]+br])\n",
    "            if l<m-1:\n",
    "                add(l+1,r)\n",
    "                if r>0:\n",
    "                    add(l+1,r-1)\n",
    "            if r<n-1:\n",
    "                add(l,r+1)\n",
    "                if l>0:\n",
    "                    add(l-1,r+1)\n",
    "        return res\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:#优先队列+多路归并\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        #初始化tuple列表\n",
    "        hq =  [(nums1[i]+nums2[0],i,0) for i in range(len(nums1))]\n",
    "        res = []\n",
    "        while len(res) < k and  hq:#如果k大于m*n，hq会空\n",
    "            Sum,i,j = heapq.heappop(hq)#拿出当前最小值的索引\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            if j+1 < n:#还没到底\n",
    "                #在当前行被抽出来的位置用下一个补位\n",
    "                heapq.heappush(hq,(nums1[i]+nums2[j+1],i,j+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        class Item:\n",
    "            def __init__(self, i, j):\n",
    "                self.i, self.j = i, j\n",
    "\n",
    "            def __lt__(self, other):\n",
    "                return True if nums1[self.i] + nums2[self.j] < nums1[other.i] + nums2[other.j] else False\n",
    "\n",
    "        priority_q = []\n",
    "        for i in range(min(k, len(nums1))):\n",
    "            heapq.heappush(priority_q, Item(i, 0))\n",
    "\n",
    "        ret = []\n",
    "        while len(ret) < k and len(priority_q) > 0:\n",
    "            largest_one = priority_q[0]\n",
    "            heapq.heappop(priority_q)\n",
    "            i, j = largest_one.i, largest_one.j\n",
    "            ret.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < len(nums2): heapq.heappush(priority_q, Item(i, j + 1))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        def heap_sort_once(nums, i, n):\n",
    "            while True:\n",
    "                leftchild = 2*i\n",
    "                rightchild = 2*i+1\n",
    "                if leftchild>=n:\n",
    "                    break\n",
    "                if rightchild < n and nums[rightchild][0] < nums[leftchild][0]:\n",
    "                    leftchild = rightchild\n",
    "                if nums[leftchild][0] < nums[i][0]:\n",
    "                    nums[i], nums[leftchild] = nums[leftchild], nums[i]\n",
    "                else:\n",
    "                    break\n",
    "                i = leftchild\n",
    "        def insert_to_heap(nums):\n",
    "            # print(nums)\n",
    "            n = len(nums)\n",
    "            i = n-1\n",
    "            while True:\n",
    "                parent = i//2\n",
    "                if nums[parent][0] <= nums[i][0]:\n",
    "                    break\n",
    "                nums[parent],nums[i] = nums[i],nums[parent]\n",
    "                i = parent\n",
    "        def datagen(i):\n",
    "            n = len(nums2)\n",
    "            for j in range(n):\n",
    "                pair = [nums1[i], nums2[j]]\n",
    "                yield pair\n",
    "            yield \"Finish\"\n",
    "        m = len(nums1)\n",
    "        datagens = {}\n",
    "        for i in range(min(m,k)):\n",
    "            datagens[i] = datagen(i)\n",
    "        heap = []\n",
    "        for i,dg in datagens.items():\n",
    "            pair = next(dg)\n",
    "            sumv = sum(pair)\n",
    "            heap.append((sumv,i,pair))\n",
    "            insert_to_heap(heap)\n",
    "        # print(heap)\n",
    "        results = []\n",
    "        while True:\n",
    "            heaproot_v, heaproot_i,heaproot_pair = heap[0]\n",
    "            heap[0],heap[-1]=heap[-1],heap[0]\n",
    "            heap.pop()\n",
    "            heap_sort_once(heap, 0, len(heap))\n",
    "            \n",
    "            results.append(heaproot_pair)\n",
    "            nextv = next(datagens[heaproot_i])\n",
    "            if nextv == \"Finish\":\n",
    "                del datagens[heaproot_i]\n",
    "            else:\n",
    "                heap.append((sum(nextv),heaproot_i,nextv))\n",
    "                insert_to_heap(heap)\n",
    "            if len(results)>=k:\n",
    "                break\n",
    "            if len(heap)==0:\n",
    "                break\n",
    "        return results[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        num_heap = []\n",
    "        for i in range(m):\n",
    "            heappush(num_heap, (nums1[i]+nums2[0], nums1[i], 0))\n",
    "        res = []\n",
    "        while num_heap and len(res) < k:\n",
    "            s, num, idx = heappop(num_heap)\n",
    "            res.append([num, nums2[idx]])\n",
    "            if idx + 1 < n:\n",
    "                heappush(num_heap, (num+nums2[idx+1], num, idx+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        N1 = len(nums1); N2 = len(nums2)\n",
    "        H = []\n",
    "\n",
    "        if N1 * N2 <= k:\n",
    "            res = []\n",
    "            for i in nums1:\n",
    "                for j in nums2:\n",
    "                    res.append([i,j])\n",
    "            return res\n",
    "\n",
    "        def shiftUp(pos):\n",
    "            while pos > 1:\n",
    "                c = pos // 2\n",
    "                c -= 1; pos -= 1\n",
    "                if nums1[H[c][0]]+nums2[H[c][1]] > nums1[H[pos][0]]+nums2[H[pos][1]]:\n",
    "                    H[c][0], H[pos][0] = H[pos][0], H[c][0]\n",
    "                    H[c][1], H[pos][1] = H[pos][1], H[c][1]\n",
    "                    pos = c + 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        def shiftDown(pos=1):\n",
    "            N = len(H); F = N//2\n",
    "            while pos <= F:\n",
    "                l = pos*2; r = l + 1\n",
    "                c = pos-1; l -= 1; r -= 1\n",
    "                if r < N and nums1[H[l][0]]+nums2[H[l][1]] > nums1[H[r][0]]+nums2[H[r][1]]:\n",
    "                    l, r = r, l\n",
    "                if nums1[H[c][0]]+nums2[H[c][1]] > nums1[H[l][0]]+nums2[H[l][1]]:\n",
    "                    H[c][0], H[l][0] = H[l][0], H[c][0]\n",
    "                    H[c][1], H[l][1] = H[l][1], H[c][1]\n",
    "                    pos = l + 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        for i in range(N2):\n",
    "            H.append([0, i])\n",
    "            shiftUp(len(H))\n",
    "\n",
    "        count = 0; res = []\n",
    "        while count < k:\n",
    "            t = [H[0][0],H[0][1]]\n",
    "            H[0][0], H[0][1] = H[-1][0], H[-1][1]\n",
    "            H.pop(-1)\n",
    "            shiftDown()\n",
    "\n",
    "            if t[0] + 1 < N1:\n",
    "                H.append([t[0]+1, t[1]])\n",
    "                shiftUp(len(H))\n",
    "            res.append([nums1[t[0]], nums2[t[1]]])\n",
    "            count += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        hp = []\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        for num in nums1:\n",
    "            heapq.heappush(hp, (num+nums2[0], num, 0))\n",
    "        \n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            if len(hp) == 0:\n",
    "                break\n",
    "            _, num, index = heapq.heappop(hp)\n",
    "            res.append([num, nums2[index]])\n",
    "            if index + 1 < n:\n",
    "                heapq.heappush(hp, (num+nums2[index+1], num, index+1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        for v in nums1:\n",
    "            heapq.heappush(heap, (v + nums2[0], 0))\n",
    "\n",
    "        n = len(nums2)\n",
    "        ans = []\n",
    "        while k > 0 and heap:\n",
    "            v_sum, idx = heapq.heappop(heap)\n",
    "            ans.append([v_sum - nums2[idx], nums2[idx]])\n",
    "            if idx < n - 1:\n",
    "                heapq.heappush(heap, (v_sum - nums2[idx] + nums2[idx+1], idx+1))\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        q = PriorityQueue()\n",
    "        ans = []\n",
    "        nt = []\n",
    "        for i,x in enumerate(nums1):\n",
    "            q.put((x+nums2[0],i))\n",
    "            nt.append(0)\n",
    "        for i in range(k):\n",
    "            if q.empty():\n",
    "                break\n",
    "            j,k = q.get()\n",
    "            ans.append((nums1[k],nums2[nt[k]]))\n",
    "            nt[k] += 1\n",
    "            if nt[k]<len(nums2):\n",
    "                q.put((nums1[k]+nums2[nt[k]],k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        pq = []\n",
    "        res = []\n",
    "        \n",
    "        for i in range(len(nums2)):\n",
    "            heapq.heappush(pq, (nums1[0]+nums2[i], nums1[0], nums2[i], 0))\n",
    "\n",
    "        length = k\n",
    "        while pq and length > 0:\n",
    "            s, a, b, i = heapq.heappop(pq)\n",
    "            res.append([a, b])\n",
    "            if i+1 < len(nums1):\n",
    "                heapq.heappush(pq, (nums1[i+1]+ b, nums1[i+1], b, i+1))\n",
    "            length = length - 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        heap = [(nums1[i] + nums2[0], i, 0) for i in range(len(nums1))]\n",
    "\n",
    "        len1 = len(nums1)\n",
    "        len2 = len(nums2)\n",
    "        max_v = len1 * len2\n",
    "        k = min(k, max_v)\n",
    "\n",
    "        res = []\n",
    "        for i in range(k - 1):\n",
    "            total, s1, s2 = heapq.heappop(heap)\n",
    "            res.append((nums1[s1], nums2[s2]))\n",
    "            if s2 + 1 < len2:\n",
    "                heapq.heappush(heap, (nums1[s1] + nums2[s2 + 1], s1, s2 + 1))\n",
    "        total, s1, s2 = heapq.heappop(heap)\n",
    "        res.append((nums1[s1], nums2[s2]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        for i in range(len(nums1)):\n",
    "            heapq.heappush(heap,(nums1[i]+nums2[0],nums1[i],nums2[0],0))\n",
    "        res = []\n",
    "        while heap and k > 0:\n",
    "            _,num1,num2,idx = heapq.heappop(heap)\n",
    "            res.append([num1,num2])\n",
    "            k -= 1\n",
    "            if idx + 1 < len(nums2):\n",
    "                heapq.heappush(heap,(num1+nums2[idx+1],num1,nums2[idx+1],idx+1))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        if k==1:\n",
    "            return [[nums1[0],nums1[1]]]\n",
    "        tar=False\n",
    "        n1,n2=len(nums1),len(nums2)\n",
    "        if n1>n2:\n",
    "            tar=True\n",
    "            n1,n2,nums1,nums2=n2,n1,nums2,nums1\n",
    "        # 保障 n1 < n2\n",
    "        arr=[]\n",
    "        \n",
    "        for i in range(n1):\n",
    "            heapq.heappush(\n",
    "                arr,(nums1[i]+nums2[0],i,0)\n",
    "            ) \n",
    "        ans=[]\n",
    "        while len(ans)<k and arr:\n",
    "            # 出来\n",
    "            _,i,j=heapq.heappop(\n",
    "                arr\n",
    "            )\n",
    "            if not tar:\n",
    "                ans.append([nums1[i],nums2[j]])\n",
    "            else:\n",
    "                ans.append([nums2[j],nums1[i]])\n",
    "            if j+1<n2:\n",
    "                heapq.heappush(\n",
    "                        arr,(nums1[i]+nums2[j+1],i,j+1)\n",
    "                    )\n",
    "                \n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        h = []\n",
    "        res = []\n",
    "\n",
    "        for num1 in nums1:\n",
    "            heapq.heappush(h, (num1 + nums2[0], num1, nums2[0], 0))\n",
    "\n",
    "        while k > 0 and h:\n",
    "            total, num1, num2, i2 = heapq.heappop(h)\n",
    "            new_i = i2 + 1\n",
    "\n",
    "            if new_i < len(nums2):\n",
    "                heapq.heappush(h, (num1 + nums2[new_i], num1, nums2[new_i], new_i))\n",
    "            \n",
    "            res.append([num1, num2])\n",
    "            k -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ret = []\n",
    "        \n",
    "        l1 = len(nums1)\n",
    "        l2 = len(nums2)\n",
    "\n",
    "        if l1 == 0 and l2 == 0:\n",
    "            return []\n",
    "\n",
    "        h = [(nums1[i] + nums2[0], i, 0) for i in range(l1)]\n",
    "\n",
    "        while k > 0 and h:\n",
    "            tmp = heapq.heappop(h)\n",
    "            ret.append((nums1[tmp[1]], nums2[tmp[2]]))\n",
    "\n",
    "            next_j = tmp[2] + 1\n",
    "\n",
    "            if next_j < l2:\n",
    "                heapq.heappush(h, (nums1[tmp[1]] + nums2[next_j], tmp[1], next_j))\n",
    "\n",
    "            k -= 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        n,m = len(nums1),len(nums2)\n",
    "        k = min(k,n*m)\n",
    "        q = [(nums1[i]+nums2[0],i,0) for i in range(n)]\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        while k >0:\n",
    "            _,i,j = heappop(q)\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            if j+1 <m:\n",
    "                heappush(q,(nums1[i]+nums2[j+1],i,j+1))\n",
    "            k -= 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ptr1 = 0\n",
    "        ptr2 = 0\n",
    "        res = []\n",
    "        for idx in range(len(nums2)):\n",
    "            heapq.heappush(res, (nums1[0] + nums2[idx], 0, idx))\n",
    "        ans = []\n",
    "        while res and len(ans) < k:\n",
    "            val, ptr1, ptr2 = heapq.heappop(res)\n",
    "            ans.append((nums1[ptr1], nums2[ptr2]))\n",
    "            if ptr1 + 1 < len(nums1):\n",
    "                heapq.heappush(res, (nums1[ptr1 + 1]+nums2[ptr2], ptr1+1, ptr2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        out = []\n",
    "        for i in range(len(nums1)):\n",
    "            heapq.heappush(res, (nums1[i] + nums2[0], i, 0))\n",
    "        while k > 0 and len(res) > 0:\n",
    "            mini, i, j = heapq.heappop(res)\n",
    "            out.append((nums1[i],nums2[j]))\n",
    "            if j < len(nums2) - 1:\n",
    "                heapq.heappush(res, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "            k -= 1\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        pq = [(nums1[i]+nums2[0],i,0) for i in range(len(nums1))]\n",
    "\n",
    "        cur = 0\n",
    "        while pq and cur<k:\n",
    "            _,i,j = heapq.heappop(pq)\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            cur+=1\n",
    "            if j+1<len(nums2):\n",
    "                heapq.heappush(pq, (nums1[i]+nums2[j+1],i ,j+1))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        pq = [(nums1[i]+nums2[0], i, 0) for i in range(m)]\n",
    "        while pq and len(res)<k:\n",
    "            _,i,j = heapq.heappop(pq)\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            if j+1<n:\n",
    "                heapq.heappush(pq, (nums1[i]+nums2[j+1], i, j+1))\n",
    "        return res\n",
    "\n",
    "        ## 思路：通过动态维护num1+num2的最小堆来实现，堆中元素保存（nums1[i]+nums2[j], i, j）,堆的初始化可固定nums1\n",
    "\n",
    "        # m,n = len(nums1),len(nums2)\n",
    "        # ans = []\n",
    "        # pq = [(nums1[i]+nums2[0], i, 0) for i in range(min(m,k))]\n",
    "        # while pq and len(ans)<k:\n",
    "        #     _, i,j = heappop(pq)\n",
    "        #     ans.append([nums1[i],nums2[j]])\n",
    "        #     if j+1<n:\n",
    "        #         heappush(pq,(nums1[i]+nums2[j+1],i,j+1))\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        count = set()\n",
    "        h = [(nums1[i] + nums2[0], i, 0) for i in range(m)]\n",
    "        res = []\n",
    "        while h and len(res) < k:\n",
    "            _, i, j = heapq.heappop(h)\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            if j+1 < n:\n",
    "                heapq.heappush(h,(nums1[i]+nums2[j+1], i, j+1))\n",
    "        return res\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        pq = [(nums1[i] + nums2[0], i, 0) for i in range(m)]\n",
    "\n",
    "        # pq = [(nums1[0]+nums2[0], 0, 0)]\n",
    "        while pq and len(ans) < k:\n",
    "            _, i, j = heappop(pq)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < n:\n",
    "                heappush(pq, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # 维护一个小根堆，初始值是nums1中所有数与nums2[0]的配对结果\n",
    "        # 每次取最小配对结果，取出以后如果这个数还能与新的数配对，则将新配对结果加入到堆中\n",
    "        ans = []\n",
    "        ln1, ln2 = len(nums1), len(nums2)\n",
    "        hq = [(nums1[i] + nums2[0], i, 0) for i in range(ln1)]\n",
    "        while hq and len(ans) < k:\n",
    "            # 每次取堆顶最小配对结果\n",
    "            s, i, j = heappop(hq)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            # 如果当前数nums1[i]还可以与nums2[j + 1]进行配对，那么将新的配对结果加入到堆中\n",
    "            # 这样可以保证遍历所有配对结果\n",
    "            if j + 1 < ln2:\n",
    "                heappush(hq, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # 从小到大排序，每次取出一个，假如nums2的下一个\n",
    "        m,n = len(nums1),len(nums2)\n",
    "        heap = [(nums1[i] + nums2[0],i,0) for i in range(m)]\n",
    "        heapify(heap)\n",
    "        res = []\n",
    "        while(heap and k > 0):\n",
    "            _,i,j = heappop(heap)\n",
    "            res.append([nums1[i],nums2[j]])\n",
    "            k -= 1\n",
    "            if(j + 1 < n):\n",
    "                heappush(heap,(nums1[i] + nums2[j+1],i,j+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        heap = []\n",
    "\n",
    "        x = 0\n",
    "        while x < n:\n",
    "            heappush(heap, (nums1[0] + nums2[x], 0, x))\n",
    "            x += 1\n",
    "        \n",
    "        ans = []\n",
    "        while len(ans) < k and heap:\n",
    "            v, i, j = heappop(heap)\n",
    "            ans.append([nums1[i], nums2[j]])\n",
    "            if i < m - 1:\n",
    "                heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        res = []\n",
    "        if n1==0 or n2==0:\n",
    "            return res\n",
    "        hq = [(nums1[i1]+nums2[0], i1, 0) for i1 in range(n1)]\n",
    "        heapq.heapify(hq)\n",
    "        while len(res)<k and len(hq)>0:\n",
    "            s, i1, i2 = heapq.heappop(hq)\n",
    "            res.append((nums1[i1], nums2[i2]))\n",
    "            i2 += 1\n",
    "            if i2<n2:\n",
    "                heapq.heappush(hq, (nums1[i1]+nums2[i2], i1, i2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        for i in range(len(nums2)):\n",
    "            heapq.heappush(heap, (nums1[0] + nums2[i], 0, i))\n",
    "        \n",
    "        ans = []\n",
    "        while heap and len(ans) < k:\n",
    "            print(i)\n",
    "            cur = heapq.heappop(heap)\n",
    "            ans.append((nums1[cur[1]], nums2[cur[2]]))\n",
    "\n",
    "            if cur[1] < len(nums1) - 1:\n",
    "                heapq.heappush(heap, (nums1[cur[1] + 1] + nums2[cur[2]], cur[1] + 1, cur[2]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # 思路2、归并排序：利用上两个序列是递增数组的条件，模拟成“378. 有序矩阵中第 K 小的元素”的矩阵形式，将nums1当作矩阵的行，nums2当作矩阵的列，\n",
    "        # 建立优先队列（小顶堆），归并k次得到前最k小的数\n",
    "        result = []\n",
    "        # 情况1、所有数对都要被返回\n",
    "        if len(nums1) * len(nums2) <= k:\n",
    "            for n1 in nums1:\n",
    "                for n2 in nums2:\n",
    "                    result.append([n1, n2])\n",
    "            return result\n",
    "        # 情况2、归并k次得到前最k小的数\n",
    "        que = []\n",
    "        # 初始化优先队列（小顶堆）\n",
    "        for i in range(len(nums1)):\n",
    "            heapq.heappush(que, (nums1[i] + nums2[0], i, 0))\n",
    "        # 归并k次得到前最k小的数\n",
    "        for _ in range(k):\n",
    "            _, i, j = heapq.heappop(que)\n",
    "            result.append([nums1[i], nums2[j]])\n",
    "            if j + 1 <= len(nums2) - 1:\n",
    "                heapq.heappush(que, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        return sorted(itertools.product(nums1,nums2), key=sum)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        heap = []\n",
    "        for i in range(m):\n",
    "            heapq.heappush(heap, [nums1[i] + nums2[0], i, 0])\n",
    "        while k:\n",
    "            if not heap:\n",
    "                break\n",
    "            _, a, b = heapq.heappop(heap)\n",
    "            ans.append([nums1[a], nums2[b]])\n",
    "            k -= 1\n",
    "            if b < n-1:\n",
    "                heapq.heappush(heap, [nums1[a] + nums2[b+1], a, b+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        length1 = len(nums1)\n",
    "        length2 = len(nums2)\n",
    "        heap = []\n",
    "\n",
    "        # 入堆 （总和，数组1索引，数组2索引）\n",
    "        for i in range(length1):\n",
    "            temp = (nums1[i]+nums2[0],i,0)\n",
    "            heapq.heappush(heap,temp)\n",
    "            \n",
    "        \n",
    "        res = []\n",
    "        # 限制\n",
    "        loop = min(k,length1*length2)\n",
    "\n",
    "        for j in range(loop):\n",
    "            print(j)\n",
    "            tup = heapq.heappop(heap)\n",
    "            tup_sum = tup[0]\n",
    "            tup_index1 = tup[1]\n",
    "            tup_index2 = tup[2]\n",
    "            res.append([nums1[tup_index1],nums2[tup_index2]])\n",
    "            \n",
    "            if tup_index2 < length2-1:\n",
    "                tup_next = (nums1[tup_index1]+nums2[tup_index2+1], tup_index1, tup_index2+1)\n",
    "                heapq.heappush(heap,tup_next)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        vals = []\n",
    "        for i in range(n1):\n",
    "            heapq.heappush(vals, [nums1[i] + nums2[0], i, 0])\n",
    "        ret = []\n",
    "        for _ in range(k):\n",
    "            if not vals: break\n",
    "            _, i, j = heapq.heappop(vals)\n",
    "            ret.append([nums1[i], nums2[j]])\n",
    "            if j < n2 - 1: heapq.heappush(vals, [nums1[i] + nums2[j + 1], i, j + 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self,nums1:List[int],nums2:List[int],k:int)->List[List[int]]:\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        ans,pq=[],[]\n",
    "        for i in range(0,m):        #将有序段0-n-1的首元素进队\n",
    "            heapq.heappush(pq,[nums1[i]+nums2[0],i,0])\n",
    "        print(len(pq))\n",
    "        while k>0 and len(pq)>0:               #循环k次或者队空为止\n",
    "            e=heapq.heappop(pq)             #出队元素e\n",
    "            print(\"%d,%d,%d\"%(e[0],e[1],e[2]))\n",
    "            ans.append([nums1[e[1]],nums2[e[2]]])\n",
    "            if e[2]+1<n:                    #有序段e.i没有超界时\n",
    "                heapq.heappush(pq,[nums1[e[1]]+nums2[e[2]+1],e[1],e[2]+1])\n",
    "            k-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import * \n",
    "class Solution:\n",
    "    def kSmallestPairs(self, n1: List[int], n2: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        tmp = SortedList([(n1[i] + n2[0], i, 0) for i in range(len(n1))])\n",
    "        while tmp and len(ans) < k:\n",
    "            _, i, j = tmp.pop(0)\n",
    "            ans.append([n1[i], n2[j]])\n",
    "            if j + 1 < len(n2):\n",
    "                tmp.add((n1[i] + n2[j + 1], i, j + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1, nums2, k):\n",
    "        import heapq\n",
    "        data = [[nums1[i]+nums2[0],i,0] for i in range(len(nums1))]\n",
    "        ind = 0\n",
    "        result = []\n",
    "        while ind<k:\n",
    "            min_ele = heapq.heappop(data)\n",
    "            i,j = min_ele[1],min_ele[2]\n",
    "            result.append([nums1[i],nums2[j]])\n",
    "            if j+1<len(nums2):\n",
    "                heapq.heappush(data,[nums1[i]+nums2[j+1],i,j+1])\n",
    "            ind+=1\n",
    "            if not data:\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        hq = []\n",
    "        exchanged = False\n",
    "        if len(nums1) > len(nums2):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "            exchanged = True\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        loc = [i for i in range(n)]\n",
    "        for i in range(m):\n",
    "            heapq.heappush(hq, (nums1[i]+ nums2[0], i, 0))\n",
    "        res = []\n",
    "        while hq and len(res) < k:\n",
    "            _, i, j = heapq.heappop(hq)\n",
    "            res.append([nums1[i], nums2[j]] if not exchanged else [nums2[j], nums1[i]])\n",
    "            if j + 1 < n:\n",
    "                j += 1\n",
    "                heapq.heappush(hq, (nums1[i]+nums2[j], i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        pq = []\n",
    "        res = []\n",
    "        p = 1\n",
    "        for i in range(len(nums1)):\n",
    "            heapq.heappush(pq, [nums1[i]+nums2[0], i, 0])\n",
    "        \n",
    "        while p <= k and pq:\n",
    "            sum_, i, j = heapq.heappop(pq)\n",
    "            p += 1\n",
    "            res.append([nums1[i], nums2[j]])\n",
    "            if j + 1< len(nums2):\n",
    "                heapq.heappush(pq, [nums1[i]+nums2[j+1], i, j+1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        queue = []\n",
    "        def push(i,j):\n",
    "            nonlocal queue\n",
    "            heapq.heappush(queue, [nums1[i]+nums2[j], i, j])\n",
    "        for i in range(len(nums1)):\n",
    "            push(i, 0)\n",
    "        result = []\n",
    "        while queue and k > 0:\n",
    "            k -= 1\n",
    "            _, i, j = heapq.heappop(queue)\n",
    "            result.append([nums1[i], nums2[j]])\n",
    "            if j + 1 < len(nums2):\n",
    "                push(i, j+1)\n",
    "        return result\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
